The present invention relates to digital communication where the information is transmitted in coded blocks and where coding is used both for error correction and error detection. More particularly, the invention relates to simple ways to reduce the error correcting capability in systems that have already been designed in order to improve on error detecting capability.
In wireless communications, the data to be communicated is typically transmitted in bursts. This is for instance the case for cellular systems like GSM and IS-95, and it is also the case for ad hoc systems, such as BLUETOOTH(trademark), operating in the unlicenced Industrial Scientific and Medical (ISM) band at 2.45 GHz.
For all of these kind of systems, coding is used to enhance the quality of the link. One can distinguish between two different kinds of coding: coding used for error correction and coding used for error detection. Often, both of these types of coding are employed to optimize the performance. The working procedure for the encoder and the decoder when both error correction and error detection are used is as follows. First, k information bits to be sent are encoded for error detection. This step is typically achieved by adding so-called cyclic redundancy check (CRC) bits. The total number of bits can then be represented by kxe2x80x2, where kxe2x80x2-k CRC bits have been added. The kxe2x80x2 bits are then encoded for error correction such that the total number of transmitted bits equals n. This might be done either by encoding the kxe2x80x2 bits into one single codeword consisting of n bits, or it might be done by first dividing the kxe2x80x2 bits into ns segments, and then encoding each one of these into codewords of length n/ns. In this way the rate of the complete coding scheme equals k/n. It can be seen that the parameter kxe2x80x2 is a design parameter which determines how much of the overall coding is spent on error correction and error detection, respectively. For example, in a BLUETOOTH(trademark)-compliant system, a 10-bit header (k=10) is first encoded for error detection by adding 8 CRC bits, so that kxe2x80x2=18. The code used for error detection ensures that the distance between any 18 bit codewords is at least 4 (i.e., at least 4 errors would have to occur before an incorrect header would go undetected). The 18 bits are then encoded for error correction by a (3,1) repetition code. For channel conditions in which the probability of a bit error on the channel, Pb is on the order of 0.1% (which is a reasonable level for the system to operate in), the probability of incorrectly decoding a packet header becomes very small, and the probability of accepting an erroneous header negligible.
The three repetition-coded bits (corresponding to the same original unencoded bit) together constitute a symbol. A majority decision is used when decoding the symbol, which means that so long as at least two of the three bits are correct, a correct decoding decision can be made. In the following, references to bit errors are intended to refer to errors in individual ones of the three repetition-coded bits.
The operation of the receiver is typically as follows. First error correction is performed in the decoding process. Then, the outcome of the error correction is checked by means of the error detection strategy. In the ideal case, the error correction code makes it possible to correct most of the errors in the received n bit blocks, and in this case the number of retransmissions is reduced significantly. Before the decoded codeword is accepted as correct, it is checked by the outer decoder used for error detection only. In this way, the probability of accepting an erroneous decoded codeword can ideally be made sufficiently small.
In cellular systems, the effect of interference from other users is controlled by means of cell- and frequency-planning, as well as by strict power-control. This enables one to ensure that the system will operate at or near optimal channel conditions, which in turn keeps the number of errors within reasonable values. This effectively means that although an erroneous codeword may sometimes be received, it only contains a small number of errors, so that there is a very high probability that this erroneous codeword will be detected by the code for error detection. Consequently, the probability of having an undetected error can be kept sufficiently small.
The same is not true for ad-hoc networks, such as BLUETOOTH(trademark) Although power control might be implemented in order to counteract the propagation loss, the interference is not under control in such systems. In fact, since it is quite possible for an interfering device to be much closer to the receiver than the intended transmitter is, the signal-to-interference ratio (SIR) can be extremely small (e.g., on the order of xe2x88x9220 dB). Also, for a system operating in an unlicenced band such as the 2.45 GHz band, the interferer need not be another communication device, but can also be a device with a significantly higher output power, such as a microwave oven. Again this can cause the received SIR to be more than 20 dB below the point at which the system is working properly.
Due to the possible presence of a very strong interferer in ad hoc networks, some type of spread spectrum technique is typically employed. There are essentially two ways that a spread spectrum system can mitigate interference: by interference suppression or by interference avoidance. Direct Sequence Spread Spectrum (DSSS) is an example of an interference suppression technique. Here the instantaneously used bandwidth greatly exceeds the information data rate to be communicated. The processing gain (PG) is obtained through the spreading sequence. For a multiple access system based on DSSS to work properly, it is essential that the interfering signal not be too much stronger than the desired one. This is due to the fact that the amount of suppression that it is possible to achieve is limited by the PG. This is described in J. C. Haartsen, xe2x80x9cThe Bluetooth Radio System,xe2x80x9d IEEE Personal Communications, vol. 7, No. 1, February 2000.
A multiple access technique that is based on interference avoidance is frequency hopped spread spectrum (FHSS). Unlike the case with DSSS, in FHSS the instantaneous bandwidth is on the same order as the symbol rate. The PG in FHSS is instead obtained by letting the carrier frequency hop over a total bandwidth that greatly exceeds the instantaneous one. Ideally, by making the carrier frequencies orthogonal to each other, a problem occurs only if the same carrier frequency is being used by more than one user at a particular moment in time. In practice, a problem might also occur if the users are transmitting on adjacent carrier frequencies at the same time, although the problem of two users transmitting on the same frequency (so-called co-channel interference) typically is the dominating source of performance degradation. If the different devices are hopping between the different carrier frequencies independent of one another in a pseudo-random fashion, the devices will use different carrier frequencies most of the time and will therefore avoid interfering with one another. A major advantage with the FHSS technique compared to DSSS is that the avoidance principle works even if the devices are transmitting with very different output powers. If the data is transmitted in packets, which typically is the case, this means that only a small fraction of the received packets will contain errors, and the throughput of the system will therefore be very good. For the small fraction of packets that are hit by the presence of an interferer, the large number of bit errors in the received packet makes the error correcting code virtually worthless. For example, the probability of a bit error, Pb, might very well be on the order of 20-50%. This of course means that the packet will not be correctly decoded, but what is even worse is that unless the code used for error detection is powerful enough, it might not even be detected that the received packet contains errors. Without such detection, there is no possibility to correct the situation by means of packet retransmission.
The simple explanation for this malfunction is that for relatively good channel conditions the probability of falsely accepting a packet is very small due to the combined use of an error correcting code and an error detecting code. However, if the channel conditions become very poor, the probability of falsely accepting a packet will be determined by the properties of the error detecting code only. Considering the above-mentioned BLUETOOTH(trademark) example, the probability of having an undetected error for the header may be estimated as the number of codewords divided by the total number of possible received 18 bit words, which equals:                               P                      ⊙            ⋐                          =                                            2                              ⋂                ∈                                                    2                              ⋂                i                                              =                                    2                              -                1                                      =                          0.4              ⁢                              %                .                                                                        (        1        )            
If one supposes that 1% of the packets are hit by a strong interferer in such a way that the access code is still found but the header is more or less ruined, then the probability of failing to detect that a header is erroneous is about 4xc2x710xe2x88x925. Given a packet rate of approximately 1600 packets per second on a link, there will be one falsely accepted packet header every 15 minutes. Whether this is acceptable or not depends on the consequences, which is application specific. If a falsely accepted header is not much worse than an erroneous header, then this is certainly no problem. If, however, one expects more serious problems, then this high a probability of accepting an incorrect header is unlikely to be acceptable. Unfortunately, empirical evidence indicates that the consequences of accepting an incorrect header are not as harmless as not decoding correctly.
When a system is initially designed, it can be hard to determine how much of the coding should be devoted to error correction and how much to error detection. Furthermore, after a system has been in operation for a while, it is possible for the usage to completely change over time. In either of these cases, it is desirable to be able to xe2x80x9cfine-tunexe2x80x9d how the trade-off between error correction and error detection should be done in order to give optimum performance.
It is therefore desirable to provide a mechanism that allows for the above-mentioned fine-tuning in an already designed system. It is also desirable to provide a system in which the same constituting codes can be used under very different channel conditions by simply adapting to the actual channel conditions.
It should be emphasized that the terms xe2x80x9ccomprisesxe2x80x9d and xe2x80x9ccomprisingxe2x80x9d, when used in this specification, are taken to specify the presence of stated features, integers, steps or components; but the use of these terms does not preclude the presence or addition of one or more other features, integers, steps, components or groups thereof.
In accordance with one aspect of the present invention, the foregoing and other objects are achieved in methods and apparatuses for receiving an encoded signal that comprises a plurality of received encoded signal values. In one aspect of the invention, this is done by using an error correction decoding technique to generate a plurality of decoded signals from the encoded signal, wherein the plurality of decoded signals includes one or more decoded information signals and one or more decoded error detection signals. A correction value is generated that is representative of how much correction was performed by the error correction decoding technique to generate the plurality of decoded signals. The one or more decoded error detection signals are used to generate an error detection result. The decoded information signals are then alternatively accepted or rejected as a function of the error detection result and a comparison of the correction value with a threshold value.
In some embodiments, the received encoded signal values may be binary values, and the correction value may be a Hamming weight, WH, that is generated as a function of the received encoded signal values and a corresponding plurality of comparison encoded signal values generated from the plurality of decoded signals.
In such embodiments, alternatively accepting or rejecting the decoded information signals as a function of the error detection result and the comparison of the correction value with a threshold value may comprise rejecting the decoded information signals if the error detection result indicates that the plurality of decoded signals includes an error or if the Hamming weight, WH, is greater than the threshold value; and otherwise accepting the decoded information signals.
In some alternative embodiments, the received encoded signal values may be soft decision values. In such cases, the correction value may be an estimate of a noise energy in the received encoded signal values. In another aspect of the invention, the estimate of the noise energy may be a squared Euclidean distance WEuc, that is generated as a function of the received encoded signal values and a corresponding plurality of comparison encoded signal values generated from the plurality of decoded signals.
In another aspect of the invention, the one or more decoded error detection signals comprise one or more cyclic redundancy check bits.
In yet another aspect of the invention, when the received encoded signal values are binary values, the correction value may be a value, MHEC, that represents how many of the plurality of decoded signals were generated without any correction being performed by the error correction decoding technique.
In still another aspect of the invention, alternatively accepting or rejecting the decoded information signals as a function of the error detection result and the comparison of the correction value with a threshold value may comprise rejecting the decoded information signals if the error detection result indicates that the plurality of decoded signals includes an error or if the correction value, MHEC, is less than the threshold value; and otherwise accepting the decoded information signals.